package com.edu.leetcode.dataStruct;

import java.util.Arrays;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @作者 five-five
 * @创建时间 2021/4/10
 */
public class Demo16 {
    public static void main(String[] args) {
        Demo16 demo16 = new Demo16();
        int[] ints = demo16.searchRange(new int[]{6, 6, 6}, 6);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 解题思路
     * 已数组nums = [5,7,7,8,8,10], target = 8为例
     * 返回数组 res = {-1,-1}
     * 第一步：
     * 左边：leftNums = [5,7,7] start = 0, end = 2；nums[2] < 8则直接舍弃返回
     * 右边：rightNums = [8,8,10] start = 3, end = 5
     * 第二步：分治rightNums = [8,8,10], start = 3, end = 5
     * 左边：leftNums = [8,8], start = 3, end = 4
     * 右边：rightNums=[10], start = 5, end = 5；nums[0] > 8 或者 rightNums[0] != 8 舍弃
     * 第三步：分治leftNums = [8,8], start = 3, end = 4
     * 左边：leftNums = [8], start = 3, end = 3; res[0] = 3, res[1] = 3
     * 右边：rightNums = [8], start = 4, end = 4; nums[4] > res[1] 所以 res[1] = 4
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        if (nums == null || nums.length == 0) {
            return res;
        }
        search(res, nums, 0, nums.length - 1, target);
        return res;
    }

    public void search(int[] res, int[] nums, int start, int end, int target) {
        if (start == end) {
            if (nums[start] == target) {
                if (start > res[1]) {
                    res[1] = start;
                }
                if (res[0] == -1 || start < res[0]) {
                    res[0] = start;
                }

            }
            return;
        } else if (nums[start] > target || nums[end] < target) {
            return;
        }
        int mid = (end + start) / 2;
        search(res, nums, start, mid, target);
        search(res, nums, mid + 1, end, target);
    }

}
